Proof-number search (short: PN search) is a game tree search algorithm invented by Victor Allis, with applications mostly in endgame solvers, but also for sub-goals during games.
Using a binary goal (e.g. first player wins the game), game trees of two-person perfect-information games can be mapped to an and–or tree. Maximizing nodes become OR-nodes, minimizing nodes are mapped to AND-nodes. For all nodes proof and disproof numbers are stored, and updated during the search.
The proof and disproof numbers represent lower bounds on the number of nodes to be evaluated to prove (or disprove) certain nodes. By always selecting the most proving (disproving) node to expand, an efficient search is generated.
Some variants of the like PN2, PDS-PN[1] have been developed to address the quite big memory requirements of the algorithm.